package question.solution10;

public class Solution10 {
    public boolean isMatch(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[s.length()][p.length()] = true;

        for (int i = s.length(); i >= 0; i--) {
            for (int j = p.length() - 1; j >= 0; j--) {
                boolean first_match = (i < s.length() &&
                        (p.charAt(j) == s.charAt(i) ||
                                p.charAt(j) == '.'));
                if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                    //在当前pattern下，在前面加一个字符，是否跟*前面的字符匹配，如果匹配就是true；如果不匹配，就看当前pattern删去头两个字符的匹配情况
                    dp[i][j] = dp[i][j + 2] || first_match && dp[i + 1][j];
                } else {
                    dp[i][j] = first_match && dp[i + 1][j + 1];
                }
//                printDP(dp,s,p);
            }
        }
        return dp[0][0];
    }

    private boolean charEqual(char matchChar, char p) {
        if (p == '.') {
            return true;
        }
        return matchChar == p;
    }

    private void printDP(boolean[][] dp, String text, String pattern){
        System.out.println("=============================================================");
        StringBuffer textStringBuffer = new StringBuffer("  ");
        for(int i=0;i<pattern.length();i++){
            textStringBuffer.append(pattern.charAt(i)).append(" ");
        }
        System.out.println(textStringBuffer);

        for(int i=0;i<dp.length;i++){
            StringBuffer stringBuffer = new StringBuffer();
            if(i<dp.length-1){
                stringBuffer.append(text.charAt(i)+" ");
            }else{
                stringBuffer.append("  ");
            }
            for(int j=0;j<dp[0].length;j++){
                if(dp[i][j]){
                    stringBuffer.append("T").append(" ");
                }else{
                    stringBuffer.append("F").append(" ");
                }
            }
            System.out.println(stringBuffer);
        }
    }

    public boolean test() {
        boolean test3 = isMatch("aa", "a*");
        return test3;
    }
}
